package com.cdream.basic.algorithm.leetcode.findElement;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author cdream
 */
public class Question451 {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }

        List[] buckets = new List[s.length() + 1];
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            List val = buckets[entry.getValue()];
            if (val == null) {
                List l = new ArrayList();
                l.add(entry.getKey());
                buckets[entry.getValue()] = l;
            } else {
                val.add(entry.getKey());
            }

        }
        StringBuilder sb = new StringBuilder();
        for (int i = buckets.length - 1; i >= 0; i--) {
            if (buckets[i] == null) {
                continue;
            }
            for (Object o : buckets[i]) {
                for (int i1 = 0; i1 < i; i1++) {
                    sb.append(o);
                }
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Question451().frequencySort("tree"));
    }
}
